package com.yin.myproject.arithmetic;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author Eason
 * @create 2018-04-22 21:12
 **/
public class MergeSorter {
    public static void main(String[] args) {
        int array[] = {94, 12, 34, 76, 26, 9, 0, 37, 55, 76, 37, 5, 68, 83, 90, 37, 12, 65, 76, 49};
        int[] auxArray = new int[array.length];
        MergeSorter sorter = new MergeSorter();
        int[] sort = sorter.sort(array, auxArray, 0, array.length - 1);
        System.out.println(Arrays.toString(sort));
    }

    private int[] sort(int[] array, int[] auxArray, int low, int high) {
        int dividedIndex = 0; // 分治位置索引变量
        if (low < high) {
            dividedIndex = (low + high) / 2; // 计算分治位置(采用简单的二分思想)
            sort(array, auxArray, low, dividedIndex); // 左侧递归归并排序
//            sort(array, auxArray, dividedIndex + 1, high); // 右侧递归归并排序
//            merge(array, auxArray, low, dividedIndex, high); // 合并分治结果
        }
        return array;
    }

    private void merge(int[] array, int[] auxArray, int low, int dividedIndex, int high) {
        int i = low;
        int j = dividedIndex + 1;
        int auxPointer = 0;
        while (i <= dividedIndex && j <= high) {
            if (array[i] > array[j]) {
                auxArray[auxPointer++] = array[j++];
            } else {
                auxArray[auxPointer++] = array[i++];
            }
        }
        while (i <= dividedIndex) {
            auxArray[auxPointer++] = array[i++];
        }
        while (j <= high) {
            auxArray[auxPointer++] = array[j++];
        }
        for (auxPointer = 0, i = low; i <= high; auxPointer++, i++) {
            array[i] = auxArray[auxPointer];
        }
    }
}
